import sys
import re
from typing import List, Tuple, Union, Optional, Dict, Any, Callable

# ===== 类型定义 =====
# AST节点类型
class AST:
    pass

class Atom(AST):
    def __init__(self, value: str):
        self.value = value
        
    def __repr__(self):
        return f"Atom('{self.value}')"

class ListAST(AST):
    def __init__(self, items: List[AST]):
        self.items = items
        
    def __repr__(self):
        return f"List({self.items})"

# 值类型
class Value:
    pass

class Symbol(Value):
    def __init__(self, name: str):
        self.name = name
        
    def __repr__(self):
        return f"Symbol('{self.name}')"

class Number(Value):
    def __init__(self, value: int):
        self.value = value
        
    def __repr__(self):
        return f"Number({self.value})"

class Pair(Value):
    def __init__(self, car: Value, cdr: Value):
        self.car = car
        self.cdr = cdr
        
    def __repr__(self):
        return f"Pair({self.car}, {self.cdr})"

class Nil(Value):
    _instance = None
    
    def __new__(cls):
        if cls._instance is None:
            cls._instance = super().__new__(cls)
        return cls._instance
    
    def __repr__(self):
        return "Nil"

class Bool(Value):
    def __init__(self, value: bool):
        self.value = value
        
    def __repr__(self):
        return f"Bool({self.value})"

class Lambda(Value):
    def __init__(self, params: List[str], body: AST, env: 'Env'):
        self.params = params
        self.body = body
        self.env = env
        
    def __repr__(self):
        return f"Lambda({self.params}, {self.body}, {self.env})"

class Label(Value):
    def __init__(self, name: str, value: Value):
        self.name = name
        self.value = value
        
    def __repr__(self):
        return f"Label('{self.name}', {self.value})"

# 环境类型 (别名)
Env = List[Tuple[str, Value]]

# ===== 词法分析器 =====
# Token类型
LPAREN = 'LPAREN'
RPAREN = 'RPAREN'
ATOM = 'ATOM'
QUOTE = 'QUOTE'

class Token:
    def __init__(self, type: str, value: str = None):
        self.type = type
        self.value = value
        
    def __repr__(self):
        return f"Token({self.type}, '{self.value}')" if self.value else f"Token({self.type})"

def is_space(c: str) -> bool:
    return c in ' \t\n\r'

def tokenize(s: str) -> List[Token]:
    tokens = []
    i = 0
    n = len(s)
    
    while i < n:
        if is_space(s[i]):
            i += 1
            continue
            
        if s[i] == '(':
            tokens.append(Token(LPAREN))
            i += 1
        elif s[i] == ')':
            tokens.append(Token(RPAREN))
            i += 1
        elif s[i] == "'":
            tokens.append(Token(QUOTE))
            i += 1
        else:
            start = i
            while i < n and not (is_space(s[i]) or s[i] in '()\''):
                i += 1
            tokens.append(Token(ATOM, s[start:i]))
    
    return tokens

# ===== 语法分析器 =====
class ParseError(Exception):
    pass

def parse(tokens: List[Token]) -> AST:
    tokens = tokens[:]  # 创建副本避免修改原始列表
    
    def parse_expr() -> Tuple[AST, List[Token]]:
        if not tokens:
            raise ParseError("Unexpected end of input")
            
        tok = tokens.pop(0)
        if tok.type == LPAREN:
            return parse_list()
        elif tok.type == ATOM:
            return Atom(tok.value), tokens
        elif tok.type == QUOTE:
            quoted, tokens = parse_expr()
            return ListAST([Atom("quote"), quoted]), tokens
        else:
            raise ParseError(f"Unexpected token: {tok.type}")
    
    def parse_list() -> Tuple[AST, List[Token]]:
        items = []
        while tokens and tokens[0].type != RPAREN:
            item, tokens = parse_expr()
            items.append(item)
        
        if not tokens:
            raise ParseError("Unexpected end of input in list")
        
        tokens.pop(0)  # 移除右括号
        return ListAST(items), tokens
    
    ast, remaining = parse_expr()
    if remaining:
        raise ParseError(f"Unexpected tokens after expression: {remaining}")
    return ast

# ===== 辅助函数 =====
def try_int(s: str) -> Value:
    try:
        return Number(int(s))
    except ValueError:
        return Symbol(s)

def is_true(v: Value) -> bool:
    if isinstance(v, Bool) and not v.value:
        return False
    if isinstance(v, Nil):
        return False
    return True

def ast_to_value(ast: AST) -> Value:
    if isinstance(ast, Atom):
        return try_int(ast.value)
    
    if isinstance(ast, ListAST):
        def build_list(items: List[AST]) -> Value:
            if not items:
                return Nil()
            return Pair(ast_to_value(items[0]), build_list(items[1:]))
        
        return build_list(ast.items)
    
    raise ValueError(f"Unsupported AST type: {type(ast)}")

def initial_env() -> Env:
    return []

# ===== 求值器 =====
class EvalError(Exception):
    pass

def eval_eq(lhs: Value, rhs: Value) -> Value:
    if type(lhs) != type(rhs):
        return Bool(False)
    
    if isinstance(lhs, Symbol) and isinstance(rhs, Symbol):
        return Bool(lhs.name == rhs.name)
    
    if isinstance(lhs, Number) and isinstance(rhs, Number):
        return Bool(lhs.value == rhs.value)
    
    if isinstance(lhs, Nil) and isinstance(rhs, Nil):
        return Bool(True)
    
    if isinstance(lhs, Pair) and isinstance(rhs, Pair):
        car_eq = eval_eq(lhs.car, rhs.car)
        cdr_eq = eval_eq(lhs.cdr, rhs.cdr)
        if is_true(car_eq) and is_true(cdr_eq):
            return Bool(True)
        return Bool(False)
    
    return Bool(False)

def eval(ast: AST, env: Env) -> Value:
    # 原子求值
    if isinstance(ast, Atom):
        # 在环境中查找
        for name, val in reversed(env):
            if name == ast.value:
                return val
        
        # 未找到，尝试解析为数字或符号
        return try_int(ast.value)
    
    # 空列表
    if isinstance(ast, ListAST) and not ast.items:
        return Nil()
    
    # quote特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 2 and isinstance(ast.items[0], Atom) and ast.items[0].value == "quote":
        return ast_to_value(ast.items[1])
    
    # atom特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 2 and isinstance(ast.items[0], Atom) and ast.items[0].value == "atom":
        arg_val = eval(ast.items[1], env)
        if isinstance(arg_val, Symbol) or isinstance(arg_val, Number) or isinstance(arg_val, Nil):
            return Bool(True)
        return Bool(False)
    
    # eq特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 3 and isinstance(ast.items[0], Atom) and ast.items[0].value == "eq":
        lhs_val = eval(ast.items[1], env)
        rhs_val = eval(ast.items[2], env)
        return eval_eq(lhs_val, rhs_val)
    
    # car特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 2 and isinstance(ast.items[0], Atom) and ast.items[0].value == "car":
        arg_val = eval(ast.items[1], env)
        if isinstance(arg_val, Pair):
            return arg_val.car
        if isinstance(arg_val, Nil):
            return Nil()
        raise EvalError("car: expected pair")
    
    # cdr特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 2 and isinstance(ast.items[0], Atom) and ast.items[0].value == "cdr":
        arg_val = eval(ast.items[1], env)
        if isinstance(arg_val, Pair):
            return arg_val.cdr
        if isinstance(arg_val, Nil):
            return Nil()
        raise EvalError("cdr: expected pair")
    
    # cons特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 3 and isinstance(ast.items[0], Atom) and ast.items[0].value == "cons":
        lhs_val = eval(ast.items[1], env)
        rhs_val = eval(ast.items[2], env)
        return Pair(lhs_val, rhs_val)
    
    # cond特殊形式
    if isinstance(ast, ListAST) and ast.items and isinstance(ast.items[0], Atom) and ast.items[0].value == "cond":
        for clause in ast.items[1:]:
            if not isinstance(clause, ListAST) or len(clause.items) != 2:
                raise EvalError("cond: malformed clause")
            
            test_val = eval(clause.items[0], env)
            if is_true(test_val):
                return eval(clause.items[1], env)
        raise EvalError("cond: no true clause")
    
    # lambda特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 3 and isinstance(ast.items[0], Atom) and ast.items[0].value == "lambda":
        if not isinstance(ast.items[1], ListAST):
            raise EvalError("lambda: expected parameter list")
        
        params = []
        for param in ast.items[1].items:
            if not isinstance(param, Atom):
                raise EvalError("lambda: parameter must be atom")
            params.append(param.value)
        
        return Lambda(params, ast.items[2], env.copy())  # 复制当前环境
    
    # label特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 3 and isinstance(ast.items[0], Atom) and ast.items[0].value == "label":
        if not isinstance(ast.items[1], Atom):
            raise EvalError("label: expected symbol for name")
        
        name = ast.items[1].value
        value = eval(ast.items[2], env)
        return Label(name, value)
    
    # define特殊形式
    if isinstance(ast, ListAST) and len(ast.items) == 3 and isinstance(ast.items[0], Atom) and ast.items[0].value == "define":
        if not isinstance(ast.items[1], Atom):
            raise EvalError("define: expected symbol for name")
        
        name = ast.items[1].value
        value = eval(ast.items[2], env)
        
        # 添加到环境 (覆盖已有绑定)
        for i, (n, _) in enumerate(env):
            if n == name:
                env[i] = (name, value)
                return value
        
        env.append((name, value))
        return value
    
    # 算术运算
    def arithmetic_op(op: Callable[[int, int], int], ast: ListAST) -> Value:
        if len(ast.items) != 3:
            raise EvalError(f"{ast.items[0].value}: expected two arguments")
        
        lhs_val = eval(ast.items[1], env)
        rhs_val = eval(ast.items[2], env)
        
        if not isinstance(lhs_val, Number) or not isinstance(rhs_val, Number):
            raise EvalError(f"{ast.items[0].value}: expected numbers")
        
        return Number(op(lhs_val.value, rhs_val.value))
    
    if isinstance(ast, ListAST) and ast.items and isinstance(ast.items[0], Atom):
        op_name = ast.items[0].value
        if op_name == '+':
            return arithmetic_op(lambda a, b: a + b, ast)
        if op_name == '-':
            return arithmetic_op(lambda a, b: a - b, ast)
        if op_name == '*':
            return arithmetic_op(lambda a, b: a * b, ast)
        if op_name == '/':
            return arithmetic_op(lambda a, b: a // b, ast)
    
    # 函数应用
    if isinstance(ast, ListAST):
        func_val = eval(ast.items[0], env)
        arg_vals = [eval(arg, env) for arg in ast.items[1:]]
        
        if isinstance(func_val, Lambda):
            # 创建新环境: 形参与实参绑定 + 闭包环境
            new_env = list(zip(func_val.params, arg_vals)) + func_val.env
            return eval(func_val.body, new_env)
        
        if isinstance(func_val, Label):
            # 递归解析Label值
            while isinstance(func_val, Label):
                func_val = func_val.value
            
            if isinstance(func_val, Lambda):
                # 创建新环境: 添加递归绑定 + 形参与实参绑定 + 闭包环境
                new_env = [(func_val.name, Label(func_val.name, func_val))] + \
                          list(zip(func_val.params, arg_vals)) + \
                          func_val.env
                return eval(func_val.body, new_env)
        
        raise EvalError(f"Cannot apply non-function: {func_val}")
    
    raise EvalError(f"Unsupported expression: {ast}")

# ===== 打印函数 =====
def string_of_value(v: Value) -> str:
    if isinstance(v, Symbol):
        return v.name
    if isinstance(v, Number):
        return str(v.value)
    if isinstance(v, Bool):
        return "t" if v.value else "()"
    if isinstance(v, Nil):
        return "()"
    if isinstance(v, Pair):
        parts = []
        current = v
        
        while isinstance(current, Pair):
            parts.append(string_of_value(current.car))
            current = current.cdr
        
        if isinstance(current, Nil):
            return "(" + " ".join(parts) + ")"
        else:
            return "(" + " ".join(parts) + " . " + string_of_value(current) + ")"
    if isinstance(v, Lambda):
        return f"(lambda ({' '.join(v.params)}) ...)"
    if isinstance(v, Label):
        return f"(label {v.name} ...)"
    
    return f"<unknown value: {type(v)}>"

# ===== 组合函数 =====
def s_expr_to_value(s: str, env: Env) -> Value:
    tokens = tokenize(s)
    ast = parse(tokens)
    return eval(ast, env)

# ===== 测试函数 =====
def test_builtins():
    env = initial_env()
    print("Running tests...\n")
    
    tests = [
        ("(quote a)", "a"),
        ("(quote (a b c))", "(a b c)"),
        ("(atom 'a)", "t"),
        ("(atom '(a b))", "()"),
        ("(eq 'a 'a)", "t"),
        ("(eq 'a 'b)", "()"),
        ("(car '(a b c))", "a"),
        ("(cdr '(a b c))", "(b c)"),
        ("(cons 'a '(b c))", "(a b c)"),
        ("(cond ((eq 1 2) 'a) ((eq 1 1) 'b))", "b"),
        ("()", "()"),
        ("'(1 2 3)", "(1 2 3)"),
        ("'(a b c)", "(a b c)"),
        ("(cons 'a (cons 'b ()))", "(a b)"),
        ("(cond (() 'a) ('t 'b))", "b"),
        ("(+ 3 5)", "8"),
        ("((lambda (x) (cons 'a x)) '(b c))", "(a b c)"),
        ("((lambda (x y) (cons x (cons y ()))) 'a 'b)", "(a b)"),
        ("((lambda (x) (cons (car x) (cdr x))) '(a b c))", "(a b c)"),
        ("((lambda (f x) (f x)) (lambda (y) (cons 'a y)) '(b c))", "(a b c)"),
        ("(define add3 (lambda (x) (+ x 3)))", "lambda"),
        ("(add3 5)", "8"),
        ("(define prod (label prod. (lambda (n) (cond ((eq n 0) 1) ('t (* n (prod. (- n 1))))))))", "label"),
        ("(prod 4)", "24"),
        ("(define Z (lambda (f) ((lambda (x) (f (lambda (v) ((x x) v)))) (lambda (x) (f (lambda (v) ((x x) v)))))))", "lambda"),
        ("(define fib. (lambda (g) (lambda (n) (cond ((eq n 0) 0) ((eq n 1) 1) ('t (+ (g (- n 1)) (g (- n 2))))))))", "lambda"),
        ("(define fib (Z fib.))", "lambda"),
        ("(fib 6)", "8"),
    ]
    
    for expr, expected in tests:
        try:
            result = s_expr_to_value(expr, env)
            result_str = string_of_value(result)
            print(f"测试: {expr:50} 期望: {expected:20} 结果: {result_str}")
            if result_str.startswith(expected) or expected in result_str:
                print("  [通过]")
            else:
                print("  [失败]")
        except Exception as e:
            print(f"测试: {expr} 出错: {str(e)}")

# ===== REPL =====
def repl():
    env = initial_env()
    print("Lisp REPL (输入 exit 退出)")
    
    while True:
        try:
            line = input("> ").strip()
            if line == "exit":
                print("再见!")
                break
            if not line:
                continue
                
            tokens = tokenize(line)
            ast = parse(tokens)
            result = eval(ast, env)
            print(string_of_value(result))
            
        except (ParseError, EvalError) as e:
            print(f"错误: {str(e)}")
        except EOFError:
            print("\n再见!")
            break
        except KeyboardInterrupt:
            print("\n再见!")
            break
        except Exception as e:
            print(f"意外错误: {str(e)}")

# ===== 主程序 =====
if __name__ == "__main__":
    test_builtins()
    print("\nStarting REPL...")
    repl()
